package com.fzy.leetcode.editor.cn;
//2023-03-17 13:01:06
//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
//
// Related Topics 字符串 回溯 👍 657 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class ZiFuChuanDePaiLieLcof {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    List<String> list = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        boolean[] use = new boolean[chars.length];
        Arrays.sort(chars);
        backtracking(chars,use);

        String[] ans = new String[list.size()];
        for(int i = 0;i<list.size();i++){
            ans[i] = list.get(i);
        }

        return ans;
    }

    public void backtracking(char[] chars,boolean[] user){
        if(str.length() == chars.length){
            list.add(str.toString());
            return;
        }

        for(int i = 0;i<chars.length;i++){
            if(i>0 && chars[i] == chars[i-1] && user[i-1] == false){
                continue;
            }

            if(user[i] == false){
                user[i] = true;
                str.append(chars[i]);
                backtracking(chars,user);
                str.setLength(str.length()-1);
                user[i] = false;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}